Batch 3 - Class 227 - Cryptocurrency

• (MC Chap 0, Prob 1) - There is a jar of yeast and the yeast doubles every day. It fills the jar on 30th day. When was the jar half full?
• Answer - Day 29

• Ask students what their understanding of cryptocurrency is, what does it mean?
• What is the difference between gold, cryptocurrency, and a rupee note?
• Limited supply (but not really), trust, integrity (one country can't just print more)...
• Note that there is nothing inherently valuable about gold, other than that everyone agrees that gold is valuable
• There is nothing inherently valuable about a rupee other than that people trust that it will be honored - what does honoring a "rupee" mean? Who guarantees it, what is the guarantee? Is rupee wealth, or is it a promise of wealth?
• Hence, why not a purely virtual currency? 
• Lets build our own cryptocurrency
• Lets start with a simple system to record transactions between a few friends. Each of them do shared expenses, and record that. Note that like a rupee, its a "promise to pay", which can be settled every once in a while. Lets say you create a website where anyone can update these transactions.

• Ask kids to do so on the whiteboard. There are likely to be random transactions that the other party does not confirm. That illustrates the problem with this system
• This system lacks integrity of transactions. Both people, especially the payer, should be able to confirm that this transaction is valid. 
• This requires digital signatures - equivalent of normal signatures. For now, we can assume that this is like a mail from the payer, saying that she agrees to the transaction. We are assuming that emails can't be forged. In reality, there are foolproof ways of obtaining digital signatures.
• Introduce basics of public and private key if required. Signature(Message, PrivateKey) gives the digital signature; and Verify(Message, DigSig, PublicKey) verifies it. DigSig is 256 bits, so one can't randomly guess the digital signature for a particular message. We also include a unique id on each message, so that the same message signature can't be replicated.
• So you now have a revised system and the ledger looks like 

• Whats the problem now? What if one of the people refuses to settle? How can we solve for that?
• How do we solve for that in real life? How do we prevent people from spending too much money that they don't have? We only allow them to spend what they have or what they are due to receive.
• So lets say we started everyone out with $100 of cryptocurrency (which they pay into the pool). And now they can only owe $100 plus whatever others owe them.
• What will the first lines of ledger look like? "Alice gets $100 from the pool" and so on.
• This requires the system to know and verify all transactions in order to validate a future transaction.
• This now allows someone to lead their whole life on the ledger. Remember, a rupee is only a promise to pay. A ledger is a promise to pay. There is not other "real" meaning to money of any sort! We can call them Ledger Dollars. We can exchange LDs for Rupees on an exchange just like we can exchange USD for Rupees. 
• What is the problem now? Who controls the website? How do you trust the website? In case of Rupee, we trust the central bank by fiat. How do we solve this problem?
• We let everyone keep a copy of the ledger for themselves
• What is the problem with this - how do we know which one is the true copy of the ledger? How do we ensure that all ledgers are getting updated in real time (so that they can compute the entire history when validating the last transaction)
• So when you hear a transaction, how do you accept/reject it, and be sure that everyone else will make the same decision? And for this to happen in the same sequence?
• This involves "proof of work". First, brief on Hash functions - Hash(Message)=256-bit-string. Easy to compute in forward direction. Almost impossible (computationally) to reverse engineer.
• So now if someone gives a ledger and a number, and claims that first 30 digits of the hash for that combination are 0s, then the person would be gone through 2^30, i.e. a billion hash computations to find that number (Note: it could be less or more, but its a billion expected attempts). Verifying that number, however, is easy (1 computation). This is called proof of work - that you can verify that they went through large amount of work efficiently.
• This whole computation is done on blocks of ledgers, rather than on the whole ledger. And to make sure the blocks fit in sequence, we will include the hash of previous block at top of the next one before computing the next one's hash. (So if you change one entry in one block, all the subsequent block hashes become invalid). That is why we call it Block Chain.
• So now anyone can be a block creator - they listen to transactions, assemble them into blocks, do the work to compute the special number, and then transmit the block to everyone else to add to their chain. The block creators are rewarded by small amounts of money, which they can add at top of that block. Creating blocks is called Mining, and it introduces new currency into the system.
• So multiple miners are trying to compute the special number for the same block, and whoever gets there first, gets paid. 
• What is the problem now? If you get conflicting block chains, which one do you trust? The protocol is that you trust the longest one - one where there is maximum proof of work! So instead of trusting a central authority, you trust computational work! Is this enough?
• Suppose someone wants to cheat someone by introducing a fraudulent transaction without telling others. That person would send a block just to one person. But to do so, she would have to find the special number before any other miner does. While it can happen, given the number of miners, it has very low probability. 
• At the same time, the recipient will hear other miners as well, and when those come in, this fraudulent block will get discarded (given that other miners collectively are putting in much more work than the fraud)
• Since we are adding new currency all the time, what preserves the value of your bitcoin holding? 
• The reward for mining drops geometrically, and we know that the sum of an infinite geometric series is finite. So we know what the total reward will ever be!
• Miners can also earn a transaction fee per transaction, so that they can continue to get paid.
• All this work does add to the overhead in the currency system - something that other systems are trying to optimize on.

• A 15-inch-long stick has four marks on it, dividing it into five segments of length 1,2,3,4 and 5 inches (although not necessarily in that order) to make a "ruler. Example below - using this ruler, you could measure 8 inches (between B and D) but you couldn't measure 12 inches. Prove that it is impossible to place the four marks in a manner that you can measure all integers 1 inch through 15 inches.

• Answer: There are only 15 measurements that can be made with 4 marks, and hence each number should be measurable exactly once. If 1 is next to 2,3 or 4, then there would be multiple ways of measuring 3, 4 and 5 respectively. So 1 has to be next to 5. Similarly, if 2 were next to 3 or 4, we would not have multiple ways of measuring 5 or 6, so 2 must also be next to 5. But this means that 1 or 2 can't both be at the extreme ends, which would make it impossible to measure 13 and 14. Hence proved.